Ruthmair (2021), allowing such revisits poses additional
computational challenges, which cannot be easily accom-
modated by many of the existing approaches in the litera-
ture. Indeed, by adding sufficiently many copies of the
nodes to the underlying graph, one can always reduce
revisiting truck routes to cycles; this approach, however,
does not appear to be computationally viable in practice.
Roberti and Ruthmair (2021) also state that an analysis of
the cost savings by revisits had, at the time of their writ-
ing, not been conducted yet.
In this paper, we consider a problem setting where
multiple drones can serve multiple customers per sortie.
Indeed, the benefits of deploying a fleet of drones, as
opposed to a single drone, were studied by, among
others, Murray and Raj (2020). Also, the technology to
enable the drones to deliver multiple packages during a
single sortie has already been developed (The Washing-
ton Post 2021), allowing for a speedup in delivery com-
pared with drones that can only visit one customer per
sortie. We observe that optimal solutions for TSP-mD
may require the truck to not only revisit nodes but also,
retraverse arcs of the underlying directed graph (i.e., in
the course of its tour, the truck might need to repeatedly
travel directly from customer i to customer j for some
fixed pair of customers i, j). As we show, excluding such
arc-retraversing solutions can lead to a significant
increase in the optimal value. The necessity of arc retra-
versals by the truck does not seem to have been investi-
gated in previous studies, and those studies that allow
node revisits seem to operate under the assumption that
there always exists an optimal solution without retraver-
sals. In fact, the integer programming (IP) formulation
proposed in the seminal paper by Agatz, Bouman, and
Schmidt (2018) for FSTSP with node revisits implicitly
excludes certain arc-retraversing solutions. We prove
that this implicit assumption is correct under specific
conditions, which the FSTSP setting studied by Agatz,
Bouman, and Schmidt (2018) meets. However, when
these conditions are not satisfied (e.g., when allowing
multiple customers to be visited by a single sortie), the
optimal value might increase significantly when exclud-
ing arc-retraversing solutions. We provide asymptoti-
cally tight a priori (i.e., solution-independent) and a
posteriori (i.e., solution-dependent) upper bounds on
such an increase. In particular, the optimal value can
increase by a factor of at most 1 + 2m (where m is the
number of drones) in the worst case when excluding
arc-retraversing solutions. The same worst-case increase
holds when excluding node revisits, giving a partial
answer to the question raised by Roberti and Ruthmair
(2021). Finally, we provide an approximation algo-
rithm whose approximation guarantee depends on the
speed and the number of available drones and show
that unless P � NP, no approximation algorithm can
obtain a guarantee that does not depend on these two
parameters.
The remainder of the paper is organized as follows. A
review of relevant works is presented in Section 2,
whereas the TSP-mD itself is formally defined in Section
3. In Section 4, we describe problem settings where it
suffices to consider solutions that are not arc retraver-
sing. We establish the aforementioned upper bounds on
the increase of the optimal value in Section 5. Finally,
Section 6 contains the proofs of our approximability
results. We conclude with Section 7. To prove the results
of Section 4, we solve a number of instances via a mixed-
integer linear programming (MILP) formulation; we
describe the relevant instances and provide the MILP
formulation in Appendices A and B, respectively.
2. Related Literature
In this section, we review the drone routing literature
that specifically addressed truck-drone(s) operation pro-
blems with exact methods. We further focus on settings
with a single truck that visits or delivers to customers in
parallel to the drone(s) and where the completion time is
minimized.
For a fast entry point to the literature, not exclusively
from the operations research perspective, we refer the
reader to the surveys by Otto et al. (2018), Roca-Riu and
Menendez (2019), Macrina, Pugliese, and Guerriero
(2020), Merkert and Bushell (2020), Boysen, Fedtke, and
Schwerdfeger (2021), Ding, Xin, and Chen (2021), Li et al.
(2021), and Persson (2021). For surveys with a focus on
drone applications to routing and parcel delivery, we
refer the reader to Coutinho, Battarra, and Fliege (2018),
Khoufi, Laouiti, and Adjih (2019), Chung, Sah, and Lee
(2020), Macrina et al. (2020), Moshref-Javadi and Win-
kenbach (2021), and Rojas Viloria et al. (2021) in chrono-
logical order of publication from 2018 to 2021. Finally,
we mention the instructive overview of the challenges
ahead for drone-aided routing provided by Poikonen
and Campbell (2021).
The FSTSP was introduced by Murray and Chu
(2015). They provided an MILP model and solved the
problem via heuristic methods. A two-stage decomposi-
tion for solving the FSTSP was developed by Yurek and
Ozmutlu (2018), by which they were able to solve
instances with 12 nodes to optimality within one hour of
computations. Dell’Amico, Montemanni, and Novellani
(2021b) provided two novel formulations for the FSTSP
and further refined them in a follow-up paper (Dell’A-
mico, Montemanni, and Novellani 2022). In particular,
the latter study tackled a number of variants of the prob-
lem, one of which includes sorties with the same launch
and landing location; we hereafter refer to such sorties
as loops. The same authors also proposed a branch-and-
bound algorithm capable of solving instances with up to
19 vertices in one hour of CPU time (Dell’Amico, Monte-
manni, and Novellani 2021a). Recently, Freitas, Penna,
and Toffolo (2021) proposed a novel MILP formulation
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1341
computational challenges, which cannot be easily accom-
modated by many of the existing approaches in the litera-
ture. Indeed, by adding sufficiently many copies of the
nodes to the underlying graph, one can always reduce
revisiting truck routes to cycles; this approach, however,
does not appear to be computationally viable in practice.
Roberti and Ruthmair (2021) also state that an analysis of
the cost savings by revisits had, at the time of their writ-
ing, not been conducted yet.
In this paper, we consider a problem setting where
multiple drones can serve multiple customers per sortie.
Indeed, the benefits of deploying a fleet of drones, as
opposed to a single drone, were studied by, among
others, Murray and Raj (2020). Also, the technology to
enable the drones to deliver multiple packages during a
single sortie has already been developed (The Washing-
ton Post 2021), allowing for a speedup in delivery com-
pared with drones that can only visit one customer per
sortie. We observe that optimal solutions for TSP-mD
may require the truck to not only revisit nodes but also,
retraverse arcs of the underlying directed graph (i.e., in
the course of its tour, the truck might need to repeatedly
travel directly from customer i to customer j for some
fixed pair of customers i, j). As we show, excluding such
arc-retraversing solutions can lead to a significant
increase in the optimal value. The necessity of arc retra-
versals by the truck does not seem to have been investi-
gated in previous studies, and those studies that allow
node revisits seem to operate under the assumption that
there always exists an optimal solution without retraver-
sals. In fact, the integer programming (IP) formulation
proposed in the seminal paper by Agatz, Bouman, and
Schmidt (2018) for FSTSP with node revisits implicitly
excludes certain arc-retraversing solutions. We prove
that this implicit assumption is correct under specific
conditions, which the FSTSP setting studied by Agatz,
Bouman, and Schmidt (2018) meets. However, when
these conditions are not satisfied (e.g., when allowing
multiple customers to be visited by a single sortie), the
optimal value might increase significantly when exclud-
ing arc-retraversing solutions. We provide asymptoti-
cally tight a priori (i.e., solution-independent) and a
posteriori (i.e., solution-dependent) upper bounds on
such an increase. In particular, the optimal value can
increase by a factor of at most 1 + 2m (where m is the
number of drones) in the worst case when excluding
arc-retraversing solutions. The same worst-case increase
holds when excluding node revisits, giving a partial
answer to the question raised by Roberti and Ruthmair
(2021). Finally, we provide an approximation algo-
rithm whose approximation guarantee depends on the
speed and the number of available drones and show
that unless P � NP, no approximation algorithm can
obtain a guarantee that does not depend on these two
parameters.
The remainder of the paper is organized as follows. A
review of relevant works is presented in Section 2,
whereas the TSP-mD itself is formally defined in Section
3. In Section 4, we describe problem settings where it
suffices to consider solutions that are not arc retraver-
sing. We establish the aforementioned upper bounds on
the increase of the optimal value in Section 5. Finally,
Section 6 contains the proofs of our approximability
results. We conclude with Section 7. To prove the results
of Section 4, we solve a number of instances via a mixed-
integer linear programming (MILP) formulation; we
describe the relevant instances and provide the MILP
formulation in Appendices A and B, respectively.
2. Related Literature
In this section, we review the drone routing literature
that specifically addressed truck-drone(s) operation pro-
blems with exact methods. We further focus on settings
with a single truck that visits or delivers to customers in
parallel to the drone(s) and where the completion time is
minimized.
For a fast entry point to the literature, not exclusively
from the operations research perspective, we refer the
reader to the surveys by Otto et al. (2018), Roca-Riu and
Menendez (2019), Macrina, Pugliese, and Guerriero
(2020), Merkert and Bushell (2020), Boysen, Fedtke, and
Schwerdfeger (2021), Ding, Xin, and Chen (2021), Li et al.
(2021), and Persson (2021). For surveys with a focus on
drone applications to routing and parcel delivery, we
refer the reader to Coutinho, Battarra, and Fliege (2018),
Khoufi, Laouiti, and Adjih (2019), Chung, Sah, and Lee
(2020), Macrina et al. (2020), Moshref-Javadi and Win-
kenbach (2021), and Rojas Viloria et al. (2021) in chrono-
logical order of publication from 2018 to 2021. Finally,
we mention the instructive overview of the challenges
ahead for drone-aided routing provided by Poikonen
and Campbell (2021).
The FSTSP was introduced by Murray and Chu
(2015). They provided an MILP model and solved the
problem via heuristic methods. A two-stage decomposi-
tion for solving the FSTSP was developed by Yurek and
Ozmutlu (2018), by which they were able to solve
instances with 12 nodes to optimality within one hour of
computations. Dell’Amico, Montemanni, and Novellani
(2021b) provided two novel formulations for the FSTSP
and further refined them in a follow-up paper (Dell’A-
mico, Montemanni, and Novellani 2022). In particular,
the latter study tackled a number of variants of the prob-
lem, one of which includes sorties with the same launch
and landing location; we hereafter refer to such sorties
as loops. The same authors also proposed a branch-and-
bound algorithm capable of solving instances with up to
19 vertices in one hour of CPU time (Dell’Amico, Monte-
manni, and Novellani 2021a). Recently, Freitas, Penna,
and Toffolo (2021) proposed a novel MILP formulation
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1341
for the FSTSP, by which they solved instances with up to
10 nodes in an average of less than two minutes.
Jeong, Song, and Lee (2019) proposed a mathematical
model to solve a generalization of the FSTSP that incor-
porates circle-shaped no-fly zones for drones and parcel
weights. They reported exact solutions for instances
with up to 10 customers. Luo et al. (2019), Gonz´alez-R
et al. (2020), and Ha et al. (2021) tackled variants of the
FSTSP where sorties can contain multiple customers;
Luo et al. (2019) tailored their variant to traffic patrolling
applications. Boccia et al. (2021b) and V´asquez, Angulo,
and Klapp (2021) considered a variant of the FSTSP that
further allows loops. They both solved instances with
up to 20 vertices in a reasonable amount of time, the for-
mer by a Benders decomposition and the latter via
branch-and-cut. In a follow-up paper, Boccia et al. (2021a)
also solved the FSTSP by combining a branch-and-cut pro-
cedure with a column generation procedure. Jeon et al.
(2021) introduced a variant where both delivery and
pickup demands are met by allowing every sortie to visit
one delivery and one pickup location (in this order) before
landing on the truck. They solved instances with up to
nine customers via an MILP model within 30 minutes of
CPU time on average.
Agatz, Bouman, and Schmidt (2018) introduced a vari-
ant of the FSTSP where the drone can perform loop sorties
and the truck can revisit a customer. They named this var-
iant the traveling salesman problem with a drone (TSP-D)
and proposed a model that contains a large number of
binary variables, one for each feasible truck-drone joint
operation. The same authors devised a dynamic program-
ming approach in Bouman, Agatz, and Schmidt (2018)
and solved instances with up to 16 nodes within three
hours of computations on average. Tang, van Hoeve,
and Shaw (2019) proposed a constraint programming ap-
proach for the TSP-D and solved instances with up to 18
nodes in an average of less than 10 minutes of computa-
tions. To the best of our knowledge, these three papers
are the only ones in the literature that solved a variant of
the FSTSP with a single truck and node revisits. In partic-
ular, Agatz, Bouman, and Schmidt (2018) is the only
study that proposed an IP formulation for the problem;
in Section 3, we describe arc-retraversing solutions that
are not allowed by this formulation.
There is no general consensus in the literature on
whether the TSP-D should allow node revisits, as per
the original definition in Agatz, Bouman, and Schmidt
(2018). In the remainder of this section, we classify the
references by their own definition of the TSP-D, even if
their problem settings do not exactly coincide with the
original definition of the FSTSP and the TSP-D by Mur-
ray and Chu (2015) and by Agatz, Bouman, and Schmidt
(2018), respectively. For sake of clarity, we schematically
summarize the problem settings considered in our selec-
tion of the literature in Table 1. In particular, we indicate
whether the relevant papers considered node revisits
and arc retraversals in the truck route, sorties that serve
multiple customers (also known in the literature as mul-
tivisit sorties), and loop sorties. Furthermore, the column
with the header “Metrics” indicates how the traveling
times for the truck (first letter) and the drones (second
letter) were determined, respectively. More precisely,
the letters E and M stand for the Euclidean and Manhat-
tan distances, respectively. The letter R indicates that the
distance between two nodes of the input graph was
given by the underlying road network. Finally, in the
last tab of Table 1, we indicate with the letters M, E, and
H whether the relevant studies proposed at least one
mathematical formulation, one tailored exact algorithm,
and one heuristic or metaheuristic method, respectively.
When a paper tackled a number of variants, if at least
one of them considered a certain setting (such as allow-
ing drone loops), then we check the corresponding cell
of the table.
Some studies (e.g., Schermer, Moeini, and Wendt 2020,
El-Adle, Ghoniem, and Haouari 2021) opted for exclud-
ing node revisits in the TSP-D, contrary to the original
definition by Agatz, Bouman, and Schmidt (2018). The
former proposed MILP formulations capable of directly
solving instances with up to 10 customers within one
hour of CPU time and up to 20 customers when embed-
ded in a branch-and-cut algorithm. The latter provided
an MILP model that solved instances with up to 24 nodes.
Zhu, Boyles, and Unnikrishnan (2022) tackled a variant of
the TSP-D where the truck is also an electric vehicle and
must visit recharge stations periodically. Their electric
truck is only allowed to revisit the locations correspond-
ing to recharging stations. They developed a branch-and-
price algorithm by which they solved instances with up
to 10 nodes in one hour. Finally, Roberti and Ruthmair
(2021) proposed a branch-and-price algorithm to effec-
tively solve the TSP-D without node revisits on instances
with up to 39 nodes within one hour of CPU time. The
main setting of their work considers drones with no bat-
tery limitations and prevents them from performing
loops; they also discussed variants, however, that incor-
porate limited battery endurance and loop sorties.
The FSTSP was soon generalized to the multiple
drones case. In 2019, Seifried (2019) proposed an MILP
model based on vehicle flows. Murray and Raj (2020)
solved instances with up to eight nodes via an MILP
model within one hour of computations. In their set-
ting, the launch and retrieval times for the drones are
not negligible. Dell’Amico, Montemanni, and Novel-
lani (2021c) tackled a further variant where the drones
are allowed to wait for the truck by hovering, and their
retrieval gives rise to a nested scheduling problem at
any customer location. They provided four formula-
tions and solved instances with 10 customers to opti-
mality in one hour. Jeong and Lee (2019) and Luo et al.
(2021) further allowed multiple customers in a single
sortie and solved instances with up to 10 customers in a
Morandi et al.: The TSP with Drones
1342 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
10 nodes in an average of less than two minutes.
Jeong, Song, and Lee (2019) proposed a mathematical
model to solve a generalization of the FSTSP that incor-
porates circle-shaped no-fly zones for drones and parcel
weights. They reported exact solutions for instances
with up to 10 customers. Luo et al. (2019), Gonz´alez-R
et al. (2020), and Ha et al. (2021) tackled variants of the
FSTSP where sorties can contain multiple customers;
Luo et al. (2019) tailored their variant to traffic patrolling
applications. Boccia et al. (2021b) and V´asquez, Angulo,
and Klapp (2021) considered a variant of the FSTSP that
further allows loops. They both solved instances with
up to 20 vertices in a reasonable amount of time, the for-
mer by a Benders decomposition and the latter via
branch-and-cut. In a follow-up paper, Boccia et al. (2021a)
also solved the FSTSP by combining a branch-and-cut pro-
cedure with a column generation procedure. Jeon et al.
(2021) introduced a variant where both delivery and
pickup demands are met by allowing every sortie to visit
one delivery and one pickup location (in this order) before
landing on the truck. They solved instances with up to
nine customers via an MILP model within 30 minutes of
CPU time on average.
Agatz, Bouman, and Schmidt (2018) introduced a vari-
ant of the FSTSP where the drone can perform loop sorties
and the truck can revisit a customer. They named this var-
iant the traveling salesman problem with a drone (TSP-D)
and proposed a model that contains a large number of
binary variables, one for each feasible truck-drone joint
operation. The same authors devised a dynamic program-
ming approach in Bouman, Agatz, and Schmidt (2018)
and solved instances with up to 16 nodes within three
hours of computations on average. Tang, van Hoeve,
and Shaw (2019) proposed a constraint programming ap-
proach for the TSP-D and solved instances with up to 18
nodes in an average of less than 10 minutes of computa-
tions. To the best of our knowledge, these three papers
are the only ones in the literature that solved a variant of
the FSTSP with a single truck and node revisits. In partic-
ular, Agatz, Bouman, and Schmidt (2018) is the only
study that proposed an IP formulation for the problem;
in Section 3, we describe arc-retraversing solutions that
are not allowed by this formulation.
There is no general consensus in the literature on
whether the TSP-D should allow node revisits, as per
the original definition in Agatz, Bouman, and Schmidt
(2018). In the remainder of this section, we classify the
references by their own definition of the TSP-D, even if
their problem settings do not exactly coincide with the
original definition of the FSTSP and the TSP-D by Mur-
ray and Chu (2015) and by Agatz, Bouman, and Schmidt
(2018), respectively. For sake of clarity, we schematically
summarize the problem settings considered in our selec-
tion of the literature in Table 1. In particular, we indicate
whether the relevant papers considered node revisits
and arc retraversals in the truck route, sorties that serve
multiple customers (also known in the literature as mul-
tivisit sorties), and loop sorties. Furthermore, the column
with the header “Metrics” indicates how the traveling
times for the truck (first letter) and the drones (second
letter) were determined, respectively. More precisely,
the letters E and M stand for the Euclidean and Manhat-
tan distances, respectively. The letter R indicates that the
distance between two nodes of the input graph was
given by the underlying road network. Finally, in the
last tab of Table 1, we indicate with the letters M, E, and
H whether the relevant studies proposed at least one
mathematical formulation, one tailored exact algorithm,
and one heuristic or metaheuristic method, respectively.
When a paper tackled a number of variants, if at least
one of them considered a certain setting (such as allow-
ing drone loops), then we check the corresponding cell
of the table.
Some studies (e.g., Schermer, Moeini, and Wendt 2020,
El-Adle, Ghoniem, and Haouari 2021) opted for exclud-
ing node revisits in the TSP-D, contrary to the original
definition by Agatz, Bouman, and Schmidt (2018). The
former proposed MILP formulations capable of directly
solving instances with up to 10 customers within one
hour of CPU time and up to 20 customers when embed-
ded in a branch-and-cut algorithm. The latter provided
an MILP model that solved instances with up to 24 nodes.
Zhu, Boyles, and Unnikrishnan (2022) tackled a variant of
the TSP-D where the truck is also an electric vehicle and
must visit recharge stations periodically. Their electric
truck is only allowed to revisit the locations correspond-
ing to recharging stations. They developed a branch-and-
price algorithm by which they solved instances with up
to 10 nodes in one hour. Finally, Roberti and Ruthmair
(2021) proposed a branch-and-price algorithm to effec-
tively solve the TSP-D without node revisits on instances
with up to 39 nodes within one hour of CPU time. The
main setting of their work considers drones with no bat-
tery limitations and prevents them from performing
loops; they also discussed variants, however, that incor-
porate limited battery endurance and loop sorties.
The FSTSP was soon generalized to the multiple
drones case. In 2019, Seifried (2019) proposed an MILP
model based on vehicle flows. Murray and Raj (2020)
solved instances with up to eight nodes via an MILP
model within one hour of computations. In their set-
ting, the launch and retrieval times for the drones are
not negligible. Dell’Amico, Montemanni, and Novel-
lani (2021c) tackled a further variant where the drones
are allowed to wait for the truck by hovering, and their
retrieval gives rise to a nested scheduling problem at
any customer location. They provided four formula-
tions and solved instances with 10 customers to opti-
mality in one hour. Jeong and Lee (2019) and Luo et al.
(2021) further allowed multiple customers in a single
sortie and solved instances with up to 10 customers in a
Morandi et al.: The TSP with Drones
1342 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
reasonable amount of time. The latter further took the
drones’ payload into account in the battery energy con-
sumption. Cavani, Iori, and Roberti (2021) identified a
number of symmetry-breaking and valid inequalities
and solved instances with up to 25 nodes to optimality
via branch-and-cut, with a time limit of two hours.
For sake of completeness, we also mention a number
of studies on the further generalization to the multiple
trucks case: among other ones, Kitjacharoenchai et al.
(2019), Bakir and Tinic¸ (2020), Tamke and Buscher
(2021), and Zhou et al. (2022). From the theoretical side,
Wang, Poikonen, and Golden (2017) provided several
worst-case bounds on the optimal value, involving the
number of vehicles and their relative speed.
3. Problem Statement
The TSP-mD can be defined as follows. Let N be the set
of nodes including the customer locations and the depot
(denoted by zero) and A be the set of arcs (i, j) for any
pair of distinct nodes i, j ∈ N. The resulting graph G �
(N, A) is complete and directed. A noncapacitated truck
and m identical drones cooperate to serve all the custo-
mers in N. We denote by Ndr ⊆ N and Ntr ⊆ N the sub-
sets of the locations that can be served by the drones and
by the truck, respectively. The intersection of these two
sets is not necessarily empty. The depot 0 belongs to Ntr,
and Ndr ∪ Ntr � N. Notice that if a node i ∈ N \ Ntr, then
the truck cannot traverse any of the arcs that are incident
to i. In particular, the truck cannot reach I, and thus, no
drone can be launched or retrieved at i. This assumption
is justified when the location represented by a node i ∈
N \ Ntr is unfit for truck traffic. For example, i could rep-
resent a crossing that is impractical for the truck to trav-
erse or a narrow passage. Traversing the arcs that are
incident to node i would imply the physical presence of
the truck at i, which under this interpretation of the
nodes in N \ Ntr, should be avoided.
We associate two distinct metrics ℓand ℓ′ with the arcs
in A, representing the time it takes for the truck and for
the drones, respectively, to traverse the arcs. In particular,
by defining ℓand ℓ′ as metrics, we implicitly require that
they are symmetric (i.e., ℓij � ℓji and ℓ′
ij � ℓ′
ji for all (i, j)
∈ A). We believe that the symmetry of ℓand ℓ′ is a prop-
erty that naturally holds in many practical applications,
and it is commonly required in the related literature. By
relaxing it, however, only our results in Section 4.1 and in
Appendix B would still hold in the generic case.
We assume without loss of generality that the truck
travels at unit speed; therefore, ℓij also measures the
length of arc (i, j), for every (i, j) ∈ A. We denote the
Table 1. Overview of the Problem Settings in the Related Literature
Revisits Retraversing Multiple drones Multivisit sorties Loops Metrics Method
Agatz, Bouman, and Schmidt (2018) ✓ ✓ E/E M, H
Boccia et al. (2021a) M/E M, E
Boccia et al. (2021b) ✓ E/E M, E
Bouman, Agatz, and Schmidt (2018) ✓ ✓ E/E E
Cavani, Iori, and Roberti (2021) ✓ ✓ M/E M, E
Dell’Amico, Montemanni, and Novellani (2021a) M/E M, E, H
Dell’Amico, Montemanni, and Novellani (2021b) M/E M, E
Dell’Amico, Montemanni, and Novellani (2021c) ✓ M/E M, E
Dell’Amico, Montemanni, and Novellani (2022) ✓ M/E M, E
El-Adle, Ghoniem, and Haouari (2021) E/E M, E
Freitas, Penna, and Toffolo (2021) R/E M, H
Gonz´alez-R et al. (2020) ✓ E/E M, H
Ha et al. (2021) ✓ E/E M, H
Jeon et al. (2021) M/E M, H
Jeong and Lee (2019) ✓ ✓ R/E M
Jeong, Song, and Lee (2019) M/E M, H
Luo et al. (2019) R/R M, H
Luo et al. (2021) ✓ ✓ E/E M, H
Murray and Chu (2015) R/E M, H
Murray and Raj (2020) ✓ R/E M, H
Roberti and Ruthmair (2021) ✓ M/E M, E
Schermer, Moeini, and Wendt (2020) ✓ E/E M, E
Seifried (2019) ✓ E/E M
Tang, van Hoeve, and Shaw (2019) ✓ ✓ E
V´asquez, Angulo, and Klapp (2021) ✓ E/E M, E
Yurek and Ozmutlu (2018) M/E M, H
Zhu, Boyles, and Unnikrishnan (2022) ✓ M/E M, E, H
This work ✓ ✓ ✓ ✓ ✓ E/E M
Notes. The letters E and M in the “Metrics” column stand for the Euclidean and Manhattan distances, respectively. The letter R indicates that the
distances were given by the underlying road network. In the “Method” column, we indicate with the letters M, E, and H whether the relevant
studies proposed at least one mathematical formulation, one tailored exact algorithm, and one heuristic or metaheuristic method, respectively.
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1343
drones’ payload into account in the battery energy con-
sumption. Cavani, Iori, and Roberti (2021) identified a
number of symmetry-breaking and valid inequalities
and solved instances with up to 25 nodes to optimality
via branch-and-cut, with a time limit of two hours.
For sake of completeness, we also mention a number
of studies on the further generalization to the multiple
trucks case: among other ones, Kitjacharoenchai et al.
(2019), Bakir and Tinic¸ (2020), Tamke and Buscher
(2021), and Zhou et al. (2022). From the theoretical side,
Wang, Poikonen, and Golden (2017) provided several
worst-case bounds on the optimal value, involving the
number of vehicles and their relative speed.
3. Problem Statement
The TSP-mD can be defined as follows. Let N be the set
of nodes including the customer locations and the depot
(denoted by zero) and A be the set of arcs (i, j) for any
pair of distinct nodes i, j ∈ N. The resulting graph G �
(N, A) is complete and directed. A noncapacitated truck
and m identical drones cooperate to serve all the custo-
mers in N. We denote by Ndr ⊆ N and Ntr ⊆ N the sub-
sets of the locations that can be served by the drones and
by the truck, respectively. The intersection of these two
sets is not necessarily empty. The depot 0 belongs to Ntr,
and Ndr ∪ Ntr � N. Notice that if a node i ∈ N \ Ntr, then
the truck cannot traverse any of the arcs that are incident
to i. In particular, the truck cannot reach I, and thus, no
drone can be launched or retrieved at i. This assumption
is justified when the location represented by a node i ∈
N \ Ntr is unfit for truck traffic. For example, i could rep-
resent a crossing that is impractical for the truck to trav-
erse or a narrow passage. Traversing the arcs that are
incident to node i would imply the physical presence of
the truck at i, which under this interpretation of the
nodes in N \ Ntr, should be avoided.
We associate two distinct metrics ℓand ℓ′ with the arcs
in A, representing the time it takes for the truck and for
the drones, respectively, to traverse the arcs. In particular,
by defining ℓand ℓ′ as metrics, we implicitly require that
they are symmetric (i.e., ℓij � ℓji and ℓ′
ij � ℓ′
ji for all (i, j)
∈ A). We believe that the symmetry of ℓand ℓ′ is a prop-
erty that naturally holds in many practical applications,
and it is commonly required in the related literature. By
relaxing it, however, only our results in Section 4.1 and in
Appendix B would still hold in the generic case.
We assume without loss of generality that the truck
travels at unit speed; therefore, ℓij also measures the
length of arc (i, j), for every (i, j) ∈ A. We denote the
Table 1. Overview of the Problem Settings in the Related Literature
Revisits Retraversing Multiple drones Multivisit sorties Loops Metrics Method
Agatz, Bouman, and Schmidt (2018) ✓ ✓ E/E M, H
Boccia et al. (2021a) M/E M, E
Boccia et al. (2021b) ✓ E/E M, E
Bouman, Agatz, and Schmidt (2018) ✓ ✓ E/E E
Cavani, Iori, and Roberti (2021) ✓ ✓ M/E M, E
Dell’Amico, Montemanni, and Novellani (2021a) M/E M, E, H
Dell’Amico, Montemanni, and Novellani (2021b) M/E M, E
Dell’Amico, Montemanni, and Novellani (2021c) ✓ M/E M, E
Dell’Amico, Montemanni, and Novellani (2022) ✓ M/E M, E
El-Adle, Ghoniem, and Haouari (2021) E/E M, E
Freitas, Penna, and Toffolo (2021) R/E M, H
Gonz´alez-R et al. (2020) ✓ E/E M, H
Ha et al. (2021) ✓ E/E M, H
Jeon et al. (2021) M/E M, H
Jeong and Lee (2019) ✓ ✓ R/E M
Jeong, Song, and Lee (2019) M/E M, H
Luo et al. (2019) R/R M, H
Luo et al. (2021) ✓ ✓ E/E M, H
Murray and Chu (2015) R/E M, H
Murray and Raj (2020) ✓ R/E M, H
Roberti and Ruthmair (2021) ✓ M/E M, E
Schermer, Moeini, and Wendt (2020) ✓ E/E M, E
Seifried (2019) ✓ E/E M
Tang, van Hoeve, and Shaw (2019) ✓ ✓ E
V´asquez, Angulo, and Klapp (2021) ✓ E/E M, E
Yurek and Ozmutlu (2018) M/E M, H
Zhu, Boyles, and Unnikrishnan (2022) ✓ M/E M, E, H
This work ✓ ✓ ✓ ✓ ✓ E/E M
Notes. The letters E and M in the “Metrics” column stand for the Euclidean and Manhattan distances, respectively. The letter R indicates that the
distances were given by the underlying road network. In the “Method” column, we indicate with the letters M, E, and H whether the relevant
studies proposed at least one mathematical formulation, one tailored exact algorithm, and one heuristic or metaheuristic method, respectively.
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1343
maximum speedup of the drones compared with the
truck by
α � max ℓij=ℓ′
ij : (i, j) ∈ A, ℓ′
ij > 0, and i, j ∈ Ndr ∩ Ntr
n o
:
(1)
When it further holds that ℓij � α · ℓ′
ij for all distinct
i, j ∈ Ndr ∩ Ntr, we say that the two metrics are propor-
tional. This case accurately models applications to last-
mile delivery within urban areas, where drones might
be forced to follow the existing road network by local
regulations for security, privacy, and noise pollution
concerns.
The truck route consists of a closed walk that starts and
ends at zero and serves all the nodes contained therein.
The drones can be independently launched onto airborne
routes, hereafter referred to as sorties, and retrieved by the
truck at the nodes on its route. Accordingly, we represent
a sortie πby a tuple of nodes (i1, : : : , ir), with r ≥ 3, where
i1, ir ∈ Ntr, and i2, : : : , ir�1 ∈ Ndr. The nodes i1 and ir repre-
sent the starting and ending nodes of π, respectively. The
set {i2, : : : , ir�1}, which we denote by N[π], represents the
nodes that are served by the drone while flying along π.
The drone can serve multiple customers in a single sortie.
The amount of energy required to perform a sortie π �
(i1, : : : , ir) is given by
wdr · Xr�1
q�1
ℓ′
iq iq+1 + Xr�1
p�2
wip · Xp�1
q�1
ℓ′
iqiq+1
0
@
1
A, (2)
where wdr is the weight of a single drone and wi ≥ 0 is
the payload to serve the customer at node i for every
i ∈ N[π]. The energy consumed by any sortie must not
exceed the maximum value B > 0 allowed by the battery,
and every time a drone lands, its battery is swapped
with a fully charged one in a negligible amount of time.
It is good practice to choose a value B that underesti-
mates the actual total energy contained in the battery of
the drones. Indeed, one can significantly prolong the life
of electrical batteries by not fully depleting them before
recharging. Moreover, when a drone arrives at the desti-
nation node of a sortie before the truck, we allow it to
land and to wait for the truck on the ground; this policy,
however, might give rise to security concerns, which can
be addressed by keeping a sufficient level of battery to
operate the drone sensors, cameras, and wireless con-
nection until the truck arrives. Alternatively, if serving a
customer by a drone already implies that the relevant
drone lands at the corresponding location (for instance,
for package delivery), we can let the drone wait on the
ground there before it flies to the ending location of the
sortie without exposing it to further security risks.
We denote the set of the feasible sorties by P. By a
slight abuse of notation, we denote by ℓ′
πthe duration of
a feasible sortie π(i.e., ℓ′
π � Pr�1
q�1 ℓ′
iqiq+1 ). By setting wi � 0
for every node i ∈ Ndr in the energy consumption (2), we
obtain that ℓ′
π ≤ B=wdr for every π ∈ P; we denote this
upper bound on the duration of the feasible sorties by L.
Notice that, because of the energy consumption (2), it
might be infeasible to reverse the order of the nodes of a
sortie, as illustrated in Figure 1; with wdr � 10, B � 350,
and a payload wC � 5 at customer C, the energy con-
sumption of the sortie on the left is 300 + 10 · 5 � 350 ≤ B,
whereas the one of its inverted counterpart is 300+
20 · 5 � 400 > B. We refer to such sorties as noninvertible.
The invertibility of the sorties is a crucial property in the
results of Section 4; in fact, this property is satisfied by
most of the settings in the related literature.
In the TSP-mD, both the truck and the drones are
allowed to wait for each other at customer locations. The
whole operation is complete when all the customers are
served and both the truck and the drones have returned
to the depot. We minimize the completion time. Figure 2
shows a feasible solution of an instance with 10 nodes
(including the depot A) and three drones.
In line with the FSTSP variant of Agatz, Bouman, and
Schmidt (2018), we allow the truck to visit customers
multiple times. Note that this also opens the possibility
for the truck to traverse the same arc multiple times (i.e.,
there may be pairs of customers i, j such that the truck
travels directly from customer i to customer j on multi-
ple occasions throughout its tour). We refer to solutions
in which this happens as arc retraversing. Figure 3 shows
an example of an (optimal) arc-retraversing solution for
an instance with five nodes and two drones. Notice that
the truck can traverse the same edge {i, j} twice in the
two opposite directions (i, j) and (j, i) without retraver-
sing the same arc. In Section 4.1, we describe instances
where all the optimal solutions are arc retraversing.
Consequently, it is necessary to allow this type of solu-
tions in our problem statement.
We observe that some arc-retraversing solutions are
not feasible in the IP model of Agatz, Bouman, and
Schmidt (2018). In particular, the solution space of the
latter IP does not include any solutions in which the
truck traverses the same arc twice when during both tra-
versals, the drone is not airborne. Indeed, the two dis-
tinct traversals of the same arc constitute identical
operations and thus, correspond to the same binary vari-
able. In Section 4.2, we prove that in the FSTSP model
Figure 1. (Color online) A Couple of Sorties, One Being the
Inversion of the Other
Note. When wdr � 10, wC � 5, and B � 350, the sortie in the right panel
is infeasible.
Morandi et al.: The TSP with Drones
1344 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
truck by
α � max ℓij=ℓ′
ij : (i, j) ∈ A, ℓ′
ij > 0, and i, j ∈ Ndr ∩ Ntr
n o
:
(1)
When it further holds that ℓij � α · ℓ′
ij for all distinct
i, j ∈ Ndr ∩ Ntr, we say that the two metrics are propor-
tional. This case accurately models applications to last-
mile delivery within urban areas, where drones might
be forced to follow the existing road network by local
regulations for security, privacy, and noise pollution
concerns.
The truck route consists of a closed walk that starts and
ends at zero and serves all the nodes contained therein.
The drones can be independently launched onto airborne
routes, hereafter referred to as sorties, and retrieved by the
truck at the nodes on its route. Accordingly, we represent
a sortie πby a tuple of nodes (i1, : : : , ir), with r ≥ 3, where
i1, ir ∈ Ntr, and i2, : : : , ir�1 ∈ Ndr. The nodes i1 and ir repre-
sent the starting and ending nodes of π, respectively. The
set {i2, : : : , ir�1}, which we denote by N[π], represents the
nodes that are served by the drone while flying along π.
The drone can serve multiple customers in a single sortie.
The amount of energy required to perform a sortie π �
(i1, : : : , ir) is given by
wdr · Xr�1
q�1
ℓ′
iq iq+1 + Xr�1
p�2
wip · Xp�1
q�1
ℓ′
iqiq+1
0
@
1
A, (2)
where wdr is the weight of a single drone and wi ≥ 0 is
the payload to serve the customer at node i for every
i ∈ N[π]. The energy consumed by any sortie must not
exceed the maximum value B > 0 allowed by the battery,
and every time a drone lands, its battery is swapped
with a fully charged one in a negligible amount of time.
It is good practice to choose a value B that underesti-
mates the actual total energy contained in the battery of
the drones. Indeed, one can significantly prolong the life
of electrical batteries by not fully depleting them before
recharging. Moreover, when a drone arrives at the desti-
nation node of a sortie before the truck, we allow it to
land and to wait for the truck on the ground; this policy,
however, might give rise to security concerns, which can
be addressed by keeping a sufficient level of battery to
operate the drone sensors, cameras, and wireless con-
nection until the truck arrives. Alternatively, if serving a
customer by a drone already implies that the relevant
drone lands at the corresponding location (for instance,
for package delivery), we can let the drone wait on the
ground there before it flies to the ending location of the
sortie without exposing it to further security risks.
We denote the set of the feasible sorties by P. By a
slight abuse of notation, we denote by ℓ′
πthe duration of
a feasible sortie π(i.e., ℓ′
π � Pr�1
q�1 ℓ′
iqiq+1 ). By setting wi � 0
for every node i ∈ Ndr in the energy consumption (2), we
obtain that ℓ′
π ≤ B=wdr for every π ∈ P; we denote this
upper bound on the duration of the feasible sorties by L.
Notice that, because of the energy consumption (2), it
might be infeasible to reverse the order of the nodes of a
sortie, as illustrated in Figure 1; with wdr � 10, B � 350,
and a payload wC � 5 at customer C, the energy con-
sumption of the sortie on the left is 300 + 10 · 5 � 350 ≤ B,
whereas the one of its inverted counterpart is 300+
20 · 5 � 400 > B. We refer to such sorties as noninvertible.
The invertibility of the sorties is a crucial property in the
results of Section 4; in fact, this property is satisfied by
most of the settings in the related literature.
In the TSP-mD, both the truck and the drones are
allowed to wait for each other at customer locations. The
whole operation is complete when all the customers are
served and both the truck and the drones have returned
to the depot. We minimize the completion time. Figure 2
shows a feasible solution of an instance with 10 nodes
(including the depot A) and three drones.
In line with the FSTSP variant of Agatz, Bouman, and
Schmidt (2018), we allow the truck to visit customers
multiple times. Note that this also opens the possibility
for the truck to traverse the same arc multiple times (i.e.,
there may be pairs of customers i, j such that the truck
travels directly from customer i to customer j on multi-
ple occasions throughout its tour). We refer to solutions
in which this happens as arc retraversing. Figure 3 shows
an example of an (optimal) arc-retraversing solution for
an instance with five nodes and two drones. Notice that
the truck can traverse the same edge {i, j} twice in the
two opposite directions (i, j) and (j, i) without retraver-
sing the same arc. In Section 4.1, we describe instances
where all the optimal solutions are arc retraversing.
Consequently, it is necessary to allow this type of solu-
tions in our problem statement.
We observe that some arc-retraversing solutions are
not feasible in the IP model of Agatz, Bouman, and
Schmidt (2018). In particular, the solution space of the
latter IP does not include any solutions in which the
truck traverses the same arc twice when during both tra-
versals, the drone is not airborne. Indeed, the two dis-
tinct traversals of the same arc constitute identical
operations and thus, correspond to the same binary vari-
able. In Section 4.2, we prove that in the FSTSP model
Figure 1. (Color online) A Couple of Sorties, One Being the
Inversion of the Other
Note. When wdr � 10, wC � 5, and B � 350, the sortie in the right panel
is infeasible.
Morandi et al.: The TSP with Drones
1344 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
studied by Agatz, Bouman, and Schmidt (2018), at least
one optimal solution is not arc retraversing, and hence,
the formulation indeed finds an optimal solution. How-
ever, as soon as the FSTSP is generalized as to incorpo-
rate payloads, multiple customers per sortie or multiple
drones, excluding arc-retraversing solutions, may lead
to excluding all optimal solutions.
We distinguish between the TSP-mD and the two
restrictions where arcs cannot be retraversed (m-CIR-
CUIT) and nodes cannot be revisited (m-CYCLE). Their
optimal values are related by
TSP-mD ≤ m-CIRCUIT ≤ m-CYCLE ≤ TSP, (3)
where TSP refers to the traveling salesman problem.
The definitions of these restrictions of the TSP-mD are
functional to the results of Section 5.
4. Arc-Retraversing Solutions
In this section, we describe instances for which all the
optimal solutions are arc retraversing (Section 4.1) and
provide conditions under which there always exists an
optimal solution that is not arc retraversing (Section 4.2).
4.1. Necessity of Arc-Retraversing Solutions
We prove that it is necessary to include arc-retraversing
solutions in the solution space of the TSP-mD by describ-
ing instances whose optimal solutions are all arc retraver-
sing. We show two instances that possess this property,
with Euclidean metrics and all-zero payloads. The first
instance has a single drone (Proposition 4.1), whereas
the second one satisfies N � Ntr � Ndr (Proposition 4.2).
The proofs of the corresponding results require us to
solve the TSP-mD a number of times. In Appendix B, we
Figure 2. (Color online) A Feasible Solution for an Instance with 10 Nodes, Three Drones, and Proportional Metrics with
α � 4=3
Note. The routes of the truck and the drones (upper panel) and the corresponding Gantt chart (lower panel) are shown.
Figure 3. (Color online) An Optimal Solution of an Instance with Five Nodes, L � 28.0, and Proportional Metrics with α � 4=3
Note. The truck traverses arc (B, C) twice.
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1345
one optimal solution is not arc retraversing, and hence,
the formulation indeed finds an optimal solution. How-
ever, as soon as the FSTSP is generalized as to incorpo-
rate payloads, multiple customers per sortie or multiple
drones, excluding arc-retraversing solutions, may lead
to excluding all optimal solutions.
We distinguish between the TSP-mD and the two
restrictions where arcs cannot be retraversed (m-CIR-
CUIT) and nodes cannot be revisited (m-CYCLE). Their
optimal values are related by
TSP-mD ≤ m-CIRCUIT ≤ m-CYCLE ≤ TSP, (3)
where TSP refers to the traveling salesman problem.
The definitions of these restrictions of the TSP-mD are
functional to the results of Section 5.
4. Arc-Retraversing Solutions
In this section, we describe instances for which all the
optimal solutions are arc retraversing (Section 4.1) and
provide conditions under which there always exists an
optimal solution that is not arc retraversing (Section 4.2).
4.1. Necessity of Arc-Retraversing Solutions
We prove that it is necessary to include arc-retraversing
solutions in the solution space of the TSP-mD by describ-
ing instances whose optimal solutions are all arc retraver-
sing. We show two instances that possess this property,
with Euclidean metrics and all-zero payloads. The first
instance has a single drone (Proposition 4.1), whereas
the second one satisfies N � Ntr � Ndr (Proposition 4.2).
The proofs of the corresponding results require us to
solve the TSP-mD a number of times. In Appendix B, we
Figure 2. (Color online) A Feasible Solution for an Instance with 10 Nodes, Three Drones, and Proportional Metrics with
α � 4=3
Note. The routes of the truck and the drones (upper panel) and the corresponding Gantt chart (lower panel) are shown.
Figure 3. (Color online) An Optimal Solution of an Instance with Five Nodes, L � 28.0, and Proportional Metrics with α � 4=3
Note. The truck traverses arc (B, C) twice.
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1345
provide the MILP model by which we solve the relevant
instances.
Proposition 4.1. There exists an instance with a single
drone, all-zero payloads, and Euclidean metrics such that
all the optimal solutions are arc retraversing.
Proof. The proof is complete if we can find an instance
with Euclidean metrics, all-zero payloads, and m � 1
and the two feasible solutions S1 and S2 such that S1 is
optimal under the further restriction that no arc can be
retraversed; the respective objective function values
OBJ1 and OBJ2 satisfy OBJ1 > OBJ2.
Such an instance is described in Appendix A.2 and
shown in Figures 4 and 5; these figures represent solu-
tions S1 and S2, and their objective function values OBJ1
and OBJ2 amount to 1,084.09 and 1,050.36, respectively.
These solutions were obtained by solving the MILP model
in Appendix B to optimality by a commercial solver. w
Notice that, in the instance shown in Figure 4, the
truck and the drones are not allowed to visit all the
nodes (i.e., Ntr ≠ N and Ndr ≠ N). An analogous result
to Proposition 4.1 also holds when N � Ndr � Ntr, even
when the feasible sorties serve only one customer.
Proposition 4.2. There exists an instance with Euclidean
metrics and all-zero payloads such that N � Ndr � Ntr, the
feasible sorties only serve one customer, and all the optimal
solutions are arc retraversing.
Proof. We follow an analogous argument to that of
Proposition 4.1. Consider the instance described in
Appendix A.3 and shown in Figures 3 and 6. On the
Figure 4. (Color online) An Optimal Solution of an Instance with 15 Nodes, Proportional Metrics with α� 1, and L � 43.04
When the Truck Is Further Constrained to Traverse an Arc at Most Once
Note. The truck and the drone can visit the nodes in Ntr � {A, F, G, H, I} and Ndr � {B, C, D, E, J, K, L, M, N, O}, respectively.
Figure 5. (Color online) A Feasible Solution of the Instance Shown in Figure 4 Without Any Constraints on the Number of Tra-
versals of Any Arc
Morandi et al.: The TSP with Drones
1346 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
instances.
Proposition 4.1. There exists an instance with a single
drone, all-zero payloads, and Euclidean metrics such that
all the optimal solutions are arc retraversing.
Proof. The proof is complete if we can find an instance
with Euclidean metrics, all-zero payloads, and m � 1
and the two feasible solutions S1 and S2 such that S1 is
optimal under the further restriction that no arc can be
retraversed; the respective objective function values
OBJ1 and OBJ2 satisfy OBJ1 > OBJ2.
Such an instance is described in Appendix A.2 and
shown in Figures 4 and 5; these figures represent solu-
tions S1 and S2, and their objective function values OBJ1
and OBJ2 amount to 1,084.09 and 1,050.36, respectively.
These solutions were obtained by solving the MILP model
in Appendix B to optimality by a commercial solver. w
Notice that, in the instance shown in Figure 4, the
truck and the drones are not allowed to visit all the
nodes (i.e., Ntr ≠ N and Ndr ≠ N). An analogous result
to Proposition 4.1 also holds when N � Ndr � Ntr, even
when the feasible sorties serve only one customer.
Proposition 4.2. There exists an instance with Euclidean
metrics and all-zero payloads such that N � Ndr � Ntr, the
feasible sorties only serve one customer, and all the optimal
solutions are arc retraversing.
Proof. We follow an analogous argument to that of
Proposition 4.1. Consider the instance described in
Appendix A.3 and shown in Figures 3 and 6. On the
Figure 4. (Color online) An Optimal Solution of an Instance with 15 Nodes, Proportional Metrics with α� 1, and L � 43.04
When the Truck Is Further Constrained to Traverse an Arc at Most Once
Note. The truck and the drone can visit the nodes in Ntr � {A, F, G, H, I} and Ndr � {B, C, D, E, J, K, L, M, N, O}, respectively.
Figure 5. (Color online) A Feasible Solution of the Instance Shown in Figure 4 Without Any Constraints on the Number of Tra-
versals of Any Arc
Morandi et al.: The TSP with Drones
1346 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
one hand, the solution shown in Figure 6 is optimal
under the condition that no arc-retraversing solutions
are allowed and leads to a completion time of 76.14;
on the other hand, that of Figure 3 (which is optimal
and retraverses one arc) leads to a strictly lower com-
pletion time, namely 62.42. w
For the instance shown in Figures 3 and 6, not allow-
ing arc-retraversing solutions leads to an increase of 18%
of the optimal completion time.
4.2. Sufficiency of Nonarc-Retraversing Solutions
In this section, we provide conditions under which there
exists an optimal solution that is not arc retraversing.
The proofs of the corresponding propositions require a
couple of intermediate results. We begin by considering
the most general setting of the TSP-mD, namely, with
multiple drones that can serve multiple customers per
sortie and without conditions on the sets Ndr and Ntr.
We then impose certain conditions on the problem
input; in the corresponding settings, we prove the suffi-
ciency of the solutions that are not arc retraversing.
Lemma 4.1. There exists an optimal solution such that if a
node i ∈ N \ {0} is visited multiple times, then a drone is
launched or retrieved every time the truck visits i.
Proof. Suppose by contradiction that a node i ∈
N \ {0} is visited multiple times, but during one of
these times, no drone is launched or retrieved. Then,
we can shortcut the truck route at i, without missing
any drone operations, and the resulting route will not
be strictly longer than the original one. w
An analogous result to Lemma 4.1 applies to the depot
as well, starting from its third visit on (the first two visits
being the start and the end of the whole operation).
Given a feasible solution represented by a truck route πtr
and drone sorties, we define the support of a sortie πdr as
the subroute π′ ⊆ πtr traversed by the truck when a
drone flies along πdr. For example, in Figure 7, the sup-
ports of the sorties (B, G, D), (D, H, K, D), (D, I, L, F), (F, J, B)
are (B, C, D), D, (D, E, F), and the arc (F, B), respectively.
We now restrict to the setting where only a single
drone is available (but can serve multiple customers per
sortie).
Lemma 4.2. Let m � 1. There exists an optimal solution
such that if an arc (i, j) ∈ A is traversed multiple times,
then the following conditions hold.
i. If the support of a sortie π′ contains (i, j), then the sup-
port of π′ is equal to arc (i, j).
ii. If the support of a sortie π′ shares at least one arc with
a truck subroute πji from j to i between two consecutive tra-
versals of (i, j), then the support of π′ is contained in πji.
Proof. If the support of a sortie π′ contains (i, j) and at
least one more arc, then the truck visits either i or j
Figure 6. (Color online) An Optimal Solution of the Instance Shown in Figure 3 When the Truck Is Constrained Not to Traverse
Any Arc More Than Once
Figure 7. (Color online) Illustration of the Definition of Sup-
port of a Sortie
Note. The numbers indicate the positions of the corresponding arcs in
the truck route.
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1347
under the condition that no arc-retraversing solutions
are allowed and leads to a completion time of 76.14;
on the other hand, that of Figure 3 (which is optimal
and retraverses one arc) leads to a strictly lower com-
pletion time, namely 62.42. w
For the instance shown in Figures 3 and 6, not allow-
ing arc-retraversing solutions leads to an increase of 18%
of the optimal completion time.
4.2. Sufficiency of Nonarc-Retraversing Solutions
In this section, we provide conditions under which there
exists an optimal solution that is not arc retraversing.
The proofs of the corresponding propositions require a
couple of intermediate results. We begin by considering
the most general setting of the TSP-mD, namely, with
multiple drones that can serve multiple customers per
sortie and without conditions on the sets Ndr and Ntr.
We then impose certain conditions on the problem
input; in the corresponding settings, we prove the suffi-
ciency of the solutions that are not arc retraversing.
Lemma 4.1. There exists an optimal solution such that if a
node i ∈ N \ {0} is visited multiple times, then a drone is
launched or retrieved every time the truck visits i.
Proof. Suppose by contradiction that a node i ∈
N \ {0} is visited multiple times, but during one of
these times, no drone is launched or retrieved. Then,
we can shortcut the truck route at i, without missing
any drone operations, and the resulting route will not
be strictly longer than the original one. w
An analogous result to Lemma 4.1 applies to the depot
as well, starting from its third visit on (the first two visits
being the start and the end of the whole operation).
Given a feasible solution represented by a truck route πtr
and drone sorties, we define the support of a sortie πdr as
the subroute π′ ⊆ πtr traversed by the truck when a
drone flies along πdr. For example, in Figure 7, the sup-
ports of the sorties (B, G, D), (D, H, K, D), (D, I, L, F), (F, J, B)
are (B, C, D), D, (D, E, F), and the arc (F, B), respectively.
We now restrict to the setting where only a single
drone is available (but can serve multiple customers per
sortie).
Lemma 4.2. Let m � 1. There exists an optimal solution
such that if an arc (i, j) ∈ A is traversed multiple times,
then the following conditions hold.
i. If the support of a sortie π′ contains (i, j), then the sup-
port of π′ is equal to arc (i, j).
ii. If the support of a sortie π′ shares at least one arc with
a truck subroute πji from j to i between two consecutive tra-
versals of (i, j), then the support of π′ is contained in πji.
Proof. If the support of a sortie π′ contains (i, j) and at
least one more arc, then the truck visits either i or j
Figure 6. (Color online) An Optimal Solution of the Instance Shown in Figure 3 When the Truck Is Constrained Not to Traverse
Any Arc More Than Once
Figure 7. (Color online) Illustration of the Definition of Sup-
port of a Sortie
Note. The numbers indicate the positions of the corresponding arcs in
the truck route.
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1347
without launching or retrieving the drone. Then, by
Lemma 4.1, we can shortcut its route at the redundant
node without losing optimality.
Suppose that a sortie π′ shares at least one arc with
a truck subroute πji, like in the hypothesis. Without
loss of generality, we can assume that the arcs shared
by both π′ and πji are only traversed once. Indeed, if
not, then the thesis holds by step (i). If the support of
π′ contains an arc that does not belong to πji, then the
truck must visit either i or j while the drone is air-
borne. Again, by Lemma 4.1, we can shortcut the
truck route at the redundant node without losing
optimality. w
Figure 8 illustrates the thesis of Lemma 4.2. In this
example, the support of sorties (B, G, C) and (B, J, F, C) is
the arc (B, C), and the supports of sorties (C, H, D) and
(D, K, I, B) are the truck subroutes (C, D) and (D, E, B),
respectively.
We make use of Lemmas 4.1 and 4.2 to prove two suf-
ficiency results for the solutions that are not arc retraver-
sing. Both the results consider a single drone that can
only perform invertible sorties.
Proposition 4.3. At least one optimal solution is not arc
retraversing if only a single drone is available, all sorties
are invertible, and they serve at most one customer.
Proof. Consider an optimal solution with the proper-
ties described in Lemma 4.2, and denote its truck
route by π. Without loss of generality, suppose that at
least one arc in πis traversed multiple times (if not,
there is nothing to prove); we choose one and denote
it by (i, j). The proof is complete if we show that there
always exists another truck route π′ that does not lead
to a (strictly) longer completion time and that tra-
verses (with multiplicity) two arcs less than π.
Because the truck travels from i to j at least twice,
its route must contain a path from j to i, between two
consecutive traversals of (i, j), that we denote by πji.
Then, we call π0i and πj0 the paths from the depot
to i and from j to the depot, respectively, such that
π � π0i ◦ (i, j) ◦ πji ◦ (i, j) ◦ πj0. Because we only have
one drone, Lemma 4.2 implies that the supports of all
the sorties performed while the truck travels along (i,
j) or πji are contained in (i, j) and πji, respectively.
Because sorties are invertible by hypothesis, we can
invert both the truck route πji and the sorties whose
support is contained in it; we call the resulting
inverted route π�1
ji . The new truck route defined by
π0i ◦ π�1
ji ◦ πj0 does not miss any drone operations
whose supports were originally contained in π0i, πji,
or πj0; however, by defining the arc (i, j) out of the
new route twice, we might miss all those sorties
whose supports were originally the arc (i, j) (at most
two of them because we removed (i, j) twice, and only
a single drone is available).
Because we are only allowed to visit one customer
per sortie, such sorties must be of the form (i, k, j), for
some intermediate customer k ∈ Ndr \ {i, j}. If ℓ′
ik ≤ ℓ′
kj,
then at node i, as soon as the truck has traveled along
π0i and would otherwise be ready to leave i, we can
instead launch the drone back and forth from i to k
and let the truck wait for it at i. Otherwise, we can
launch the drone back and forth from j to k, immedi-
ately after the truck has traveled along π�1
ji . These
(possibly two) new sorties are by construction not lon-
ger than the original sorties of the form (i, k, j). Hence,
they are feasible, and when incorporated into the new
truck route π′ � π0i ◦ π�1
ji ◦ πj0, they lead to a comple-
tion time that is not greater than π’s original one. In
this solution, the truck traverses (with multiplicity)
two arcs less than π. w
The idea of the transformation π ⊢→ π′ is depicted in
Figure 9. The three conditions on Proposition 4.3 are met
by most of the problem settings in the related literature;
this fact justifies their implicit assumption that arc-
retraversing solutions do not lead to a strictly lower
completion time. Moreover, these conditions are mini-
mal. Indeed, Proposition 4.3 does not hold when two
drones are available (as implied by the solutions shown
in Figures 3 and 6), sorties are noninvertible (in particu-
lar, the inverted path π�1
ji might require the drone to fly
along infeasible sorties), or sorties serve two customers
(see Figure 5). For example, in the problem setting of
Agatz, Bouman, and Schmidt (2018), Proposition 4.3
holds, and therefore, it is correct to solve the problem via
an IP model that does not allow arc-retraversing solu-
tions. However, if we wanted to generalize the setting so
as to incorporate multiple drones or payloads in the
energy consumption of a sortie, then excluding arc-
retraversing solutions may lead to a strictly higher
Figure 8. (Color online) Illustration of the Thesis of Lemma
4.2
Morandi et al.: The TSP with Drones
1348 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
Lemma 4.1, we can shortcut its route at the redundant
node without losing optimality.
Suppose that a sortie π′ shares at least one arc with
a truck subroute πji, like in the hypothesis. Without
loss of generality, we can assume that the arcs shared
by both π′ and πji are only traversed once. Indeed, if
not, then the thesis holds by step (i). If the support of
π′ contains an arc that does not belong to πji, then the
truck must visit either i or j while the drone is air-
borne. Again, by Lemma 4.1, we can shortcut the
truck route at the redundant node without losing
optimality. w
Figure 8 illustrates the thesis of Lemma 4.2. In this
example, the support of sorties (B, G, C) and (B, J, F, C) is
the arc (B, C), and the supports of sorties (C, H, D) and
(D, K, I, B) are the truck subroutes (C, D) and (D, E, B),
respectively.
We make use of Lemmas 4.1 and 4.2 to prove two suf-
ficiency results for the solutions that are not arc retraver-
sing. Both the results consider a single drone that can
only perform invertible sorties.
Proposition 4.3. At least one optimal solution is not arc
retraversing if only a single drone is available, all sorties
are invertible, and they serve at most one customer.
Proof. Consider an optimal solution with the proper-
ties described in Lemma 4.2, and denote its truck
route by π. Without loss of generality, suppose that at
least one arc in πis traversed multiple times (if not,
there is nothing to prove); we choose one and denote
it by (i, j). The proof is complete if we show that there
always exists another truck route π′ that does not lead
to a (strictly) longer completion time and that tra-
verses (with multiplicity) two arcs less than π.
Because the truck travels from i to j at least twice,
its route must contain a path from j to i, between two
consecutive traversals of (i, j), that we denote by πji.
Then, we call π0i and πj0 the paths from the depot
to i and from j to the depot, respectively, such that
π � π0i ◦ (i, j) ◦ πji ◦ (i, j) ◦ πj0. Because we only have
one drone, Lemma 4.2 implies that the supports of all
the sorties performed while the truck travels along (i,
j) or πji are contained in (i, j) and πji, respectively.
Because sorties are invertible by hypothesis, we can
invert both the truck route πji and the sorties whose
support is contained in it; we call the resulting
inverted route π�1
ji . The new truck route defined by
π0i ◦ π�1
ji ◦ πj0 does not miss any drone operations
whose supports were originally contained in π0i, πji,
or πj0; however, by defining the arc (i, j) out of the
new route twice, we might miss all those sorties
whose supports were originally the arc (i, j) (at most
two of them because we removed (i, j) twice, and only
a single drone is available).
Because we are only allowed to visit one customer
per sortie, such sorties must be of the form (i, k, j), for
some intermediate customer k ∈ Ndr \ {i, j}. If ℓ′
ik ≤ ℓ′
kj,
then at node i, as soon as the truck has traveled along
π0i and would otherwise be ready to leave i, we can
instead launch the drone back and forth from i to k
and let the truck wait for it at i. Otherwise, we can
launch the drone back and forth from j to k, immedi-
ately after the truck has traveled along π�1
ji . These
(possibly two) new sorties are by construction not lon-
ger than the original sorties of the form (i, k, j). Hence,
they are feasible, and when incorporated into the new
truck route π′ � π0i ◦ π�1
ji ◦ πj0, they lead to a comple-
tion time that is not greater than π’s original one. In
this solution, the truck traverses (with multiplicity)
two arcs less than π. w
The idea of the transformation π ⊢→ π′ is depicted in
Figure 9. The three conditions on Proposition 4.3 are met
by most of the problem settings in the related literature;
this fact justifies their implicit assumption that arc-
retraversing solutions do not lead to a strictly lower
completion time. Moreover, these conditions are mini-
mal. Indeed, Proposition 4.3 does not hold when two
drones are available (as implied by the solutions shown
in Figures 3 and 6), sorties are noninvertible (in particu-
lar, the inverted path π�1
ji might require the drone to fly
along infeasible sorties), or sorties serve two customers
(see Figure 5). For example, in the problem setting of
Agatz, Bouman, and Schmidt (2018), Proposition 4.3
holds, and therefore, it is correct to solve the problem via
an IP model that does not allow arc-retraversing solu-
tions. However, if we wanted to generalize the setting so
as to incorporate multiple drones or payloads in the
energy consumption of a sortie, then excluding arc-
retraversing solutions may lead to a strictly higher
Figure 8. (Color online) Illustration of the Thesis of Lemma
4.2
Morandi et al.: The TSP with Drones
1348 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
completion time. An analogous result to Proposition 4.3
also holds in a slightly different setting, when the drone
does not travel faster than the truck, and can serve multi-
ple customers per sortie.
Proposition 4.4. At least one optimal solution is not arc
retraversing if only a single drone is available, all sorties
are invertible, Ntr � N, and α� 1.
Proof. Consider an optimal solution with the properties
described in Lemma 4.2, and suppose that it is arc retra-
versing. Analogously to Proposition 4.3, we denote one
of the retraversed arcs by (i, j) and the truck route by π.
Let πji, π0i, and πj0 be the analogous paths to those
defined in the proof of Proposition 4.3; accordingly,
π � π0i ◦ (i, j) ◦ πji ◦ (i, j) ◦ πj0. The proof is complete if
we show that there is always another solution π′ with
the same completion time, such that the total number of
arcs (with multiplicity) that are traversed by the truck
and the drone decreases by at least one unit.
Without loss of generality, we can assume that the
drone is airborne during at least one truck traversal of
(i, j), either immediately before the traversal of πji or
immediately after. Indeed, if not, then we remove arc
(i, j) twice from the route and invert πji (the relevant
sorties are invertible by hypothesis, and their support
is contained in πji by Lemma 4.2); the solution
induced by the truck route π′ � π0i ◦ π�1
ji ◦ πj0 is not
longer than π. Suppose that the drone flies along a
path πdr
ij during the truck traversal of arc (i, j) immedi-
ately before the traversal of πji (the proof is analogous
with the traversal of (i, j) immediately after πji). Then,
instead of launching the drone along πdr
ij , we instead
let the truck traverse it. This is feasible because
Ntr � N, and it does not take (strictly) longer than the
drone’s sortie because α� 1.
After routing the truck along πdr
ij , we follow the
original route πalong πji ◦ (i, j). The new truck route
given by π′ � π0i ◦ πdr
ij ◦ πji ◦ (i, j) ◦ πj0 is feasible and
leads to a completion time that is not (strictly) larger
than that of π. Additionally, in this solution, the total
number of arcs (with multiplicity) that are traversed
by the truck and the drone is strictly smaller than in
the original solution. w
The idea of the proof of Proposition 4.4 is shown in
Figure 10. The set of conditions required in Proposi-
tion 4.4 is minimal. Indeed, we would not be able to
replace the truck route (i, j) with πdr
ij if Ntr ≠ N or α > 1.
Sorties must be invertible to include cases where an
arc (i, j) is traversed twice by the truck while the drone
is not airborne. The route transformation π ⊢→ π′ of
Proposition 4.4 is functional to the a posteriori upper
bounds described in Section 5.2.
5. Excluding Arc-Retraversing Solutions
By excluding arc-retraversing solutions in the TSP-mD,
the optimal value might increase. In Sections 5.1 and 5.2,
we identify conditions under which a priori (i.e., solu-
tion-independent) and a posteriori (i.e., solution-depen-
dent) upper bounds hold on such increase, respectively.
5.1. A Priori Upper Bounds on the Increase of the
Completion Time
In Section 3, we have defined two restrictions of the TSP-
mD, namely the m-CYCLE and the m-CIRCUIT; by
Inequality (3), any upper bound on m-CYCLE=TSP-mD
also holds on m-CIRCUIT=TSP-mD. We identify a priori
upper bounds on the former ratio m-CYCLE=TSP-mD
that depend on m and α.
Proposition 5.1. If the truck can visit every node, then it
holds that
m-CYCLE ≤ (1 + αm)TSP-mD: (4)
Inequality (4) follows from m-CYCLE ≤ TSP and from
TSP ≤ (1 + αm)TSP-mD; the latter inequality was shown
by Wang, Poikonen, and Golden (2017) in an analogous
setting. We now describe other a priori upper bounds
that only depend on m and that dominate Inequality (4)
for all α > 2. For sake of clarity, we first prove a prelimi-
nary result by the following lemma.
Figure 9. (Color online) Illustration of the Argument of Prop-
osition 4.3
Figure 10. (Color online) Illustration of the Argument of
Proposition 4.4
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1349
also holds in a slightly different setting, when the drone
does not travel faster than the truck, and can serve multi-
ple customers per sortie.
Proposition 4.4. At least one optimal solution is not arc
retraversing if only a single drone is available, all sorties
are invertible, Ntr � N, and α� 1.
Proof. Consider an optimal solution with the properties
described in Lemma 4.2, and suppose that it is arc retra-
versing. Analogously to Proposition 4.3, we denote one
of the retraversed arcs by (i, j) and the truck route by π.
Let πji, π0i, and πj0 be the analogous paths to those
defined in the proof of Proposition 4.3; accordingly,
π � π0i ◦ (i, j) ◦ πji ◦ (i, j) ◦ πj0. The proof is complete if
we show that there is always another solution π′ with
the same completion time, such that the total number of
arcs (with multiplicity) that are traversed by the truck
and the drone decreases by at least one unit.
Without loss of generality, we can assume that the
drone is airborne during at least one truck traversal of
(i, j), either immediately before the traversal of πji or
immediately after. Indeed, if not, then we remove arc
(i, j) twice from the route and invert πji (the relevant
sorties are invertible by hypothesis, and their support
is contained in πji by Lemma 4.2); the solution
induced by the truck route π′ � π0i ◦ π�1
ji ◦ πj0 is not
longer than π. Suppose that the drone flies along a
path πdr
ij during the truck traversal of arc (i, j) immedi-
ately before the traversal of πji (the proof is analogous
with the traversal of (i, j) immediately after πji). Then,
instead of launching the drone along πdr
ij , we instead
let the truck traverse it. This is feasible because
Ntr � N, and it does not take (strictly) longer than the
drone’s sortie because α� 1.
After routing the truck along πdr
ij , we follow the
original route πalong πji ◦ (i, j). The new truck route
given by π′ � π0i ◦ πdr
ij ◦ πji ◦ (i, j) ◦ πj0 is feasible and
leads to a completion time that is not (strictly) larger
than that of π. Additionally, in this solution, the total
number of arcs (with multiplicity) that are traversed
by the truck and the drone is strictly smaller than in
the original solution. w
The idea of the proof of Proposition 4.4 is shown in
Figure 10. The set of conditions required in Proposi-
tion 4.4 is minimal. Indeed, we would not be able to
replace the truck route (i, j) with πdr
ij if Ntr ≠ N or α > 1.
Sorties must be invertible to include cases where an
arc (i, j) is traversed twice by the truck while the drone
is not airborne. The route transformation π ⊢→ π′ of
Proposition 4.4 is functional to the a posteriori upper
bounds described in Section 5.2.
5. Excluding Arc-Retraversing Solutions
By excluding arc-retraversing solutions in the TSP-mD,
the optimal value might increase. In Sections 5.1 and 5.2,
we identify conditions under which a priori (i.e., solu-
tion-independent) and a posteriori (i.e., solution-depen-
dent) upper bounds hold on such increase, respectively.
5.1. A Priori Upper Bounds on the Increase of the
Completion Time
In Section 3, we have defined two restrictions of the TSP-
mD, namely the m-CYCLE and the m-CIRCUIT; by
Inequality (3), any upper bound on m-CYCLE=TSP-mD
also holds on m-CIRCUIT=TSP-mD. We identify a priori
upper bounds on the former ratio m-CYCLE=TSP-mD
that depend on m and α.
Proposition 5.1. If the truck can visit every node, then it
holds that
m-CYCLE ≤ (1 + αm)TSP-mD: (4)
Inequality (4) follows from m-CYCLE ≤ TSP and from
TSP ≤ (1 + αm)TSP-mD; the latter inequality was shown
by Wang, Poikonen, and Golden (2017) in an analogous
setting. We now describe other a priori upper bounds
that only depend on m and that dominate Inequality (4)
for all α > 2. For sake of clarity, we first prove a prelimi-
nary result by the following lemma.
Figure 9. (Color online) Illustration of the Argument of Prop-
osition 4.3
Figure 10. (Color online) Illustration of the Argument of
Proposition 4.4
Morandi et al.: The TSP with Drones
Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS 1349
Lemma 5.1. Let π � (i1, : : : , ir) be a feasible nonloop sortie.
For every t ∈ {2, : : : , r � 1}, at least one sortie out of π1 �
(i1, : : : , it, i1) and π2 � (ir, : : : , it, ir) is feasible.
Proof. For the sake of notation, we define the quantity
ℓ(p1, p2) � Pp2�1
q�p1 ℓ′
iqiq+1 for indices p1 and p2 that satisfy
p1 < p2 ≤ r. Because πis feasible, it holds that
wdr · ℓ(1, r) + Xr�1
p�2
(wip · ℓ(1, p)) ≤ B, (5)
where the left-hand side quantifies the energy consump-
tion of π. Let t and π1 be an index and a sortie like in the
hypothesis, respectively. Suppose that π1 is not feasible.
Because ℓ′ is a metric, it holds that ℓ(1, t) ≥ ℓ′
1t. Then, the
following quantity is not lower than the energy consump-
tion of π1:
2wdr · ℓ(1, t) + Xt
p�2
(wip · ℓ(1, p))
≥ wdr · ℓ(1, t) + Xt
p�2
(wip · ℓ(1, p)) + wdr · ℓ′
t, 1 > B: (6)
We want to show that π2 � (ir, : : : , it, ir) is feasible. By
subtracting the left-hand side of Inequality (5) from
the first step of chain (6), we deduce that
wdr · ℓ(1, t) > wdr · ℓ(t, r) + Xr�1
p�t+1
(wip · ℓ(1, p)): (7)
By dropping the last term on the right-hand side of
Inequality (7), we obtain that, for every p ≥ t,
ℓ(1, p) ≥ ℓ(1, t) > ℓ(t, r) ≥ ℓ(p, r): (8)
The following chain of inequalities shows that the
energy consumption of π2 is not greater than that of
π, which in turn, implies that π2 is feasible:
wdr · (ℓ′
tr + ℓ(t, r)) + Xr�1
p�t
(wip · ℓ(p, r))
≤ 2wdr · ℓ(t, r) + Xr�1
p�t
(wip · ℓ(p, r))
≤ 2wdr · ℓ(t, r) + Xr�1
p�t
(wip · ℓ(1, p))
≤ wdr · ℓ(t, r) + wdr · ℓ(1, t) + Xr�1
p�t
(wip · ℓ(1, p))
� wdr · ℓ(1, r) + Xr�1
p�t
(wip · ℓ(1, p))
≤ wdr · ℓ(1, r) + Xr�1
p�2
(wip · ℓ(1, p)): (9)
The first step of the chain follows from the triangle
inequality, whereas the second and third steps follow
from Inequalities (8). w
Notice that, with the notation of Lemma 5.1, the sorties π,
π1, and π2 satisfy the inequality ℓ′
π1 + ℓ′
π2 ≤ 2ℓ′
πby construc-
tion. This fact is crucial to the proof of the following result.
Proposition 5.2. It holds that
m-CYCLE ≤ (1 + 2m)TSP-mD: (10)
If the feasible sorties are either loops or contain only one
customer, then it further holds that
m-CYCLE ≤ (1 + m)TSP-mD: (11)
Proof. We first prove Inequalities (10) and (11) for the case
m � 1, and we then adapt the argument to any m ≥ 2. Sup-
pose that m � 1; in this case, the proof of Inequality (10) is
complete if, for every feasible solution, we can replace every
nonloop sortie πby either a single sortie π0 or by two sor-
ties π1 and π2 that satisfy all the following conditions.
i. Sortie π0 or sorties π1 and π2 are feasible loops.
ii. It holds that N[π] � N[π0], or N[π] � N[π1] ∪
N[π2].
iii. Either inequality ℓ′
π0 ≤ 2ℓ′
πor inequality ℓ′
π1 + ℓ′
π2
≤ 2ℓ′
πholds.
Indeed, if we can always replace every nonloop sortie π
either by the corresponding π0 or by π1 and π2, then we
let the truck wait at the starting node of every sortie, and
we shortcut its route to eliminate every node revisit. The
resulting solution is feasible to the 1-CYCLE restriction,
and its objective value satisfies 1-CYCLE ≤ 3 · TSP-1D �
(1 + 2m)TSP-1D because the travel times of both the truck
and the drone are not longer than the TSP-1D objective
value and because of condition (iii).
Then, let π � (i1, : : : , ir) be a feasible nonloop sortie. We
choose the relevant sorties π0 or π1 and π2 as follows. If at
least one sortie out of (i1, : : : , ir�1, i1) and (ir, : : : , i2, ir) is
feasible, we choose one and denote it as π0. Otherwise, by
Lemma 5.1, sorties (i1, i2, i1) and (ir, ir�1, ir) are both feasi-
ble. Therefore, there exists a unique t ∈ {2, : : : , r � 2} such
that the sortie (i1, : : : , it, i1) is feasible but (i1, : : : , it+1, i1) is
not. We can then choose π1 � (i1, : : : , it, i1), and by Lemma
5.1, π2 � (ir, : : : , it+1, ir). The sorties π0 or π1 and π2 satisfy
the aforementioned conditions (i)–(iii).
If a nonloop sortie contains only a single customer
(i.e., it is of the form (i1, i2, i3)), then we can choose the
shortest arc between (i1, i2) and (i2, i3) and set π0 �
(i1, i2, i1) or π0 � (i3, i2, i3) accordingly. Notice that in
this case, it holds that ℓ′
π0 ≤ ℓ′
π. If the feasible sorties
are either loops or satisfy r � 3, an argument analo-
gous to that for the (1 + 2m) bound leads to the
inequality 1-CYCLE ≤ 2 · TSP-1D � (1 + m)TSP-1D.
If m ≥ 2, we can repeat the same construction for the
sorties of every drone, but this time, the truck has to wait
up to m times longer for all the drones to perform their
sorties. w
We complement the results of the previous proposition
by showing that Inequalities (10) and (11) are asymptotically
Morandi et al.: The TSP with Drones
1350 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS
For every t ∈ {2, : : : , r � 1}, at least one sortie out of π1 �
(i1, : : : , it, i1) and π2 � (ir, : : : , it, ir) is feasible.
Proof. For the sake of notation, we define the quantity
ℓ(p1, p2) � Pp2�1
q�p1 ℓ′
iqiq+1 for indices p1 and p2 that satisfy
p1 < p2 ≤ r. Because πis feasible, it holds that
wdr · ℓ(1, r) + Xr�1
p�2
(wip · ℓ(1, p)) ≤ B, (5)
where the left-hand side quantifies the energy consump-
tion of π. Let t and π1 be an index and a sortie like in the
hypothesis, respectively. Suppose that π1 is not feasible.
Because ℓ′ is a metric, it holds that ℓ(1, t) ≥ ℓ′
1t. Then, the
following quantity is not lower than the energy consump-
tion of π1:
2wdr · ℓ(1, t) + Xt
p�2
(wip · ℓ(1, p))
≥ wdr · ℓ(1, t) + Xt
p�2
(wip · ℓ(1, p)) + wdr · ℓ′
t, 1 > B: (6)
We want to show that π2 � (ir, : : : , it, ir) is feasible. By
subtracting the left-hand side of Inequality (5) from
the first step of chain (6), we deduce that
wdr · ℓ(1, t) > wdr · ℓ(t, r) + Xr�1
p�t+1
(wip · ℓ(1, p)): (7)
By dropping the last term on the right-hand side of
Inequality (7), we obtain that, for every p ≥ t,
ℓ(1, p) ≥ ℓ(1, t) > ℓ(t, r) ≥ ℓ(p, r): (8)
The following chain of inequalities shows that the
energy consumption of π2 is not greater than that of
π, which in turn, implies that π2 is feasible:
wdr · (ℓ′
tr + ℓ(t, r)) + Xr�1
p�t
(wip · ℓ(p, r))
≤ 2wdr · ℓ(t, r) + Xr�1
p�t
(wip · ℓ(p, r))
≤ 2wdr · ℓ(t, r) + Xr�1
p�t
(wip · ℓ(1, p))
≤ wdr · ℓ(t, r) + wdr · ℓ(1, t) + Xr�1
p�t
(wip · ℓ(1, p))
� wdr · ℓ(1, r) + Xr�1
p�t
(wip · ℓ(1, p))
≤ wdr · ℓ(1, r) + Xr�1
p�2
(wip · ℓ(1, p)): (9)
The first step of the chain follows from the triangle
inequality, whereas the second and third steps follow
from Inequalities (8). w
Notice that, with the notation of Lemma 5.1, the sorties π,
π1, and π2 satisfy the inequality ℓ′
π1 + ℓ′
π2 ≤ 2ℓ′
πby construc-
tion. This fact is crucial to the proof of the following result.
Proposition 5.2. It holds that
m-CYCLE ≤ (1 + 2m)TSP-mD: (10)
If the feasible sorties are either loops or contain only one
customer, then it further holds that
m-CYCLE ≤ (1 + m)TSP-mD: (11)
Proof. We first prove Inequalities (10) and (11) for the case
m � 1, and we then adapt the argument to any m ≥ 2. Sup-
pose that m � 1; in this case, the proof of Inequality (10) is
complete if, for every feasible solution, we can replace every
nonloop sortie πby either a single sortie π0 or by two sor-
ties π1 and π2 that satisfy all the following conditions.
i. Sortie π0 or sorties π1 and π2 are feasible loops.
ii. It holds that N[π] � N[π0], or N[π] � N[π1] ∪
N[π2].
iii. Either inequality ℓ′
π0 ≤ 2ℓ′
πor inequality ℓ′
π1 + ℓ′
π2
≤ 2ℓ′
πholds.
Indeed, if we can always replace every nonloop sortie π
either by the corresponding π0 or by π1 and π2, then we
let the truck wait at the starting node of every sortie, and
we shortcut its route to eliminate every node revisit. The
resulting solution is feasible to the 1-CYCLE restriction,
and its objective value satisfies 1-CYCLE ≤ 3 · TSP-1D �
(1 + 2m)TSP-1D because the travel times of both the truck
and the drone are not longer than the TSP-1D objective
value and because of condition (iii).
Then, let π � (i1, : : : , ir) be a feasible nonloop sortie. We
choose the relevant sorties π0 or π1 and π2 as follows. If at
least one sortie out of (i1, : : : , ir�1, i1) and (ir, : : : , i2, ir) is
feasible, we choose one and denote it as π0. Otherwise, by
Lemma 5.1, sorties (i1, i2, i1) and (ir, ir�1, ir) are both feasi-
ble. Therefore, there exists a unique t ∈ {2, : : : , r � 2} such
that the sortie (i1, : : : , it, i1) is feasible but (i1, : : : , it+1, i1) is
not. We can then choose π1 � (i1, : : : , it, i1), and by Lemma
5.1, π2 � (ir, : : : , it+1, ir). The sorties π0 or π1 and π2 satisfy
the aforementioned conditions (i)–(iii).
If a nonloop sortie contains only a single customer
(i.e., it is of the form (i1, i2, i3)), then we can choose the
shortest arc between (i1, i2) and (i2, i3) and set π0 �
(i1, i2, i1) or π0 � (i3, i2, i3) accordingly. Notice that in
this case, it holds that ℓ′
π0 ≤ ℓ′
π. If the feasible sorties
are either loops or satisfy r � 3, an argument analo-
gous to that for the (1 + 2m) bound leads to the
inequality 1-CYCLE ≤ 2 · TSP-1D � (1 + m)TSP-1D.
If m ≥ 2, we can repeat the same construction for the
sorties of every drone, but this time, the truck has to wait
up to m times longer for all the drones to perform their
sorties. w
We complement the results of the previous proposition
by showing that Inequalities (10) and (11) are asymptotically
Morandi et al.: The TSP with Drones
1350 Transportation Science, 2023, vol. 57, no. 5, pp. 1340–1358, © 2023 INFORMS